

function say() {
    alert("378. 有序矩阵中第 K 小的元素");
}
say();

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(matrix, k) {
    //11:37-52
    var row = matrix.length - 1
    var col = matrix[0].length - 1

    var left = matrix[0][0]
    var right = matrix[row][col]

    while(left < right){
        var mid = Math.floor(right + (left - right) / 2)
        //计算小于mid的数量
        var count = countSmallThanMid(matrix, mid, row, col)
        if(count < k){
            left = mid + 1
        }else {
            right = mid
        }

    }
    return left
};

//小于等于 mid 的数量
function countSmallThanMid(matrix, mid, row, col){
    var i = 0 //列
    var j = row
    var count = 0
    while(j >= 0 && i <= col){
        if(matrix[i][j] <= mid){
            count += j+1
            i ++
        }else {
            j--
        }
    }
    return count
}
